package src.leetcode.everyday.hard_3459;


/**
 * @Author: 李逸重
 * @CreateTime: 2025-08-27
 * @Description:
 * @Version: 1.0
 */
public class lenOfVDiagonal {
    public static void main(String[] args) {
        System.out.println(new Solution().lenOfVDiagonal(new int[][]{{2,2,2,2,2},{2,0,2,2,0},{2,0,1,1,0},{1,0,2,2,2},{2,0,0,2,2}}));
    }
}

class Solution {
    int[][][] mamery;
    int[][] dir = new int[][]{{-1, -1}, {-1, 1}, {1, 1}, {1, -1}};
    int ans = 0;
    int n, m;
    public int lenOfVDiagonal(int[][] grid) {
        n = grid.length; m = grid[0].length;
        mamery = new int[n][m][4];
        initMamery(grid);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans = Math.max(ans, getAns(grid, i, j));
            }
        }
        return ans;
    }

    private void initMamery(int[][] grid) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] != 0 && grid[i][j] != 2) {
                    continue;
                }
                for (int k = 0; k < 4; k++) {
                    int count = 1;
                    int prex = i, prey = j;
                    int x = i + dir[k][0], y = j + dir[k][1];
                    while (x >= 0 && x < n && y >= 0 && y < m) {
                        if (mamery[x][y][k] != 0) {
                            count += mamery[x][y][k];
                            break;
                        }
                        if (grid[x][y] + grid[prex][prey] != 2) {
                            break;
                        }
                        count++;
                        prex = x;
                        prey = y;
                        x += dir[k][0];
                        y += dir[k][1];
                    }
                    mamery[i][j][k] = count;
                }
            }
        }
    }

    private int getAns(int[][] grid, int i, int j) {
        if (grid[i][j] != 1) {
            return 0;
        }
        int res = 1;
        for (int k = 0; k < 4; k++) {
            int count = 1;
            int prex = i, prey = j;
            int x = i + dir[k][0], y = j + dir[k][1];
            while (x >= 0 && x < n && y >= 0 && y < m) {
                if (!(grid[prex][prex] == 1 && grid[x][y] == 2) && !(grid[x][y] + grid[prex][prey] == 2)) {
                    break;
                }
                res = Math.max(res, count + mamery[x][y][(k + 1) % 4]);
                res = Math.max(res, count + mamery[x][y][(k + 3) % 4]);
                count++;
                prex = x;
                prey = y;
                x += dir[k][0];
                y += dir[k][1];
            }
        }
        return res;
    }
}